1. Field of the Invention
The present invention relates to image processing systems, and more specifically, to three-dimensional rendering systems using fixed-rate image compression for textures.
2. Description of the Related Art
The art of generating images, such as realistic or animated graphics on a computer is known. To generate such images requires tremendous memory bandwidth and processing power on a graphics subsystem. To reduce the bandwidth and processing power requirements, various compression methods and systems were developed. These methods and systems included Entropy or lossless encoders, discrete cosine transform or JPEG type compressors, block truncation coding, color cell compression, and others. Each of these methods and systems, however, have numerous drawbacks.
Entropy or lossless encoders include Lempel-Ziv encoders and are used for many different purposes. Entropy coding relies on predictability. For data compression using Entropy encoders, a few bits are used to encode the most commonly occurring symbols. In stationary systems where the probabilities are fixed, Entropy coding provides a lower bound for the compression than can be achieved with a given alphabet of symbols. A problem with Entropy coding is that it does not allow random access to any given symbol. The part of the compressed data preceding a symbol of interest must be first fetched and decompressed to decode the symbol which takes considerable processing time and resources as well as decreasing memory throughput. Another problem with existing Entropy methods and systems is that they do not provide any guaranteed compression factor which makes this type of encoding scheme impractical where the memory size is fixed.
Discrete Cosine Transform ("DCT") or JPEG-type compressors, allow users to select a level of image quality. With DCT, uncorrelated coefficients are produced so that each coefficient can be treated independently without loss of compression efficiency. The DCT coefficients can be quantized using visually-weighted quantization values which selectively discard the least important information.
DCT, however, suffers from a number of shortcomings. One problem with DCT and JPEG-type compressors is that they require usually bigger blocks of pixels, typically 8.times.8 or 16.times.16 pixels, as a minimally accessible unit in order to obtain a reasonable compression factor and quality. Access to a very small area, or even a single pixel involves fetching a large quantity of compressed data, thus requiring increased processor power and memory bandwidth. A second problem with DCT and JPEG-type compressors is that the compression factor is variable, therefore requiring a complicated memory management system that, in turn, requires greater processor resources. A third problem with DCT and JPEG-type compression is that using a large compression factor significantly degrades image quality. For example, the image may be considerably distorted with a form of a ringing around the edges in the image as well as noticeable color shifts in areas of the image. Neither artifact can be removed with subsequent low-pass filtering.
A fourth problem with DCT and JPEG-type compression is that such a decompressor is complex and has a significant associated hardware cost. Further, the high latency of the decompressor results in a large additional hardware cost for buffering throughout the system to compensate for the latency. Finally, a A fifth problem with DCT and JPEG-type compressors is that it is not clear whether a color keyed image can be compressed with such a method and system.
Block truncation coding ("BTC") and color cell compression ("CCC") use a local one-bit quantizer on 4.times.4 pixel blocks. The compressed data for such a block consists of only two colors and 16-bits that indicate which one of the two colors is assigned to each of the 16 pixels. Decoding a BTC/CCC image consists of using a multiplexer with a look-up table so that once a 16-texel-block (32-bits) is retrieved from memory, the individual pixels are decoded by looking up the two possible colors for that block and selecting the color according to the associated bit from the 16 decision bits.
The BTC/CCC methods quantize each block to just two color levels resulting in significant image degradation. Further, a two-bit variation of CCC stores the two colors as eight-bit indices into a 256-entry color lookup table. Thus, such pixel blocks cannot be decoded without fetching additional information that can consume additional memory bandwidth.
The BTC/CCC methods and systems can use a three-bit per pixel scheme which store the two colors as 16-bit values (not indices into a table) resulting in pixel blocks of six bytes. Fetching such units, however, decreases system performance because of additional overhead due to memory misalignment. Another problem with BTC/CCC is that when it is used to compress images that use color keying to indicate transparent pixels, there will be a high degradation of image quality.
Therefore, there is a need for a method and system that maximizes the accuracy of compressed images while minimizing storage, memory bandwidth requirements, and decoding hardware complexities, while also compressing image data blocks into convenient sizes to maintain alignment for random access to any one or more pixels.